1. Field of the Invention
This invention relates to file systems for data storage devices including among others semiconductor memories, disc drives and tape drives, and more particularly, to such file systems which implement garbage collection processes and power fail recovery mechanisms.
2. Description of the Prior Art
In most computer systems and other intelligent computing devices, a microprocessor or central processing unit is coupled to a redundant memory storage system comprising a main memory and a secondary memory. Main memory is used for the temporary storage of information that can be quickly retrieved by the microprocessor for use in program execution. Secondary memory is typically used as an adjunct to the main memory for the long-term storage of information needed for other, non-active program applications. Accordingly, main memory storage devices typically comprise fast devices such as semiconductor memories, while secondary memory storage devices comprise slower, electro-mechanical disk storage devices.
With respect to semiconductor memory devices, such memories may include read only memory (ROM) devices which are non-volatile memories that cannot be written to or erased, random access memory (RAM) devices which are volatile, read-write memory storage devices that are electrically erasable at the byte level, and read-mostly memory devices which are non-volatile memories that can be written to, read from and are electrically erasable at either the chip level, sector level or byte level. The class of read-mostly memory devices includes optically erasable programmable read-only memory (EPROM) devices, electrically erasable programmable read-only memory (EEPROM) devices and FLASH memory devices. Although EPROM devices must be erased in their entirety at the chip level in order to reprogram or write new information to them, both EEPROM and FLASH memory devices provide greater flexibility by enabling the microprocessor to read and write information at the byte and sector levels, respectively.
Recently, prior art read-mostly memory devices have been designed to allow for the storage of data files and application programs on the purely solid-state medium. Accordingly, through the use of system resident filing systems, a read-mostly memory device can be utilized as a secondary memory for a computer system or the like to thereby reduce the relatively slow prior art upload of information from secondary to primary memory.
In prior art memory systems, usable address space is recovered through what is commonly known as a garbage collection process. Although there are a number of classical garbage collection schemes in existence, one particular scheme known as the "mark and sweep" scheme recovers the usable address space by removing older files not currently in use in a multi-phase process. During normal memory writes, storage is allocated from a free list of storage spaces until some minimum threshold of available memory storage is reached. Upon reaching the threshold, the program application is stopped and garbage collection commences. All files in memory are then traversed, and those files that are determined to be currently in use are marked in a first phase of the process. When the entire set of files has been traversed, a sweep phase is begun in which memory storage is recovered by removing all the unmarked files.
The benefit of the mark and sweep scheme is that no dead files survive the garbage collection process, and the entire memory storage allocated can be used for storage. However, a negative aspect of this scheme is that memory fragmentation can become a serious problem unless compaction or an elaborate multi-space allocation is performed. Yet, if file compaction is used, the memory system is left in a dangerous, inconsistent state throughout the garbage collection process. This is because the occurrence of a power failure or other type of system failure during the garbage collection process will cause the microprocessor managing the memory system to stall upon reboot and file system initialization since the data files are at that time dispersed throughout memory.